﻿////// 面试题 08.06. 汉诺塔问题
////// https://leetcode.cn/problems/hanota-lcci/
////
////// 注意审题啊！！！！！！！！！！！一开始都在第一个柱子上，而且注意有顺序
////
/////*
////n = 1: 1 -> 3
////n = 2: 上面的借助3到2，然后1 -> 3, 2 -> 3
////n = 3: 要先把最底下的上面的两个给移到2上，和n = 2时一样，要把上面的两个借助3移到2上，再把1->3,再把2上的2个借助1->3
////
////1、搞清子问题 ---> 函数头
////a, b, c, n
////
////2、搞清子问题解法 ---> 函数体
////把a上的n - 1个盘子借助3移到2上 ---> 把a上的一个盘子移到c上 --> 把b上的n - 1个盘子借助a移到c上
////dfs(a, c, b, n - 1)// a上的n - 1个盘子借助c移到b上
////a->c// a上的盘子移到c上
////dfs(b, a, c, n - 1)// b上的n - 1个盘子借助a移到c上
////
////3、注意结束
////n == 1时，a -> c
////*/
////
////class Solution {
////public:
////    void dfs(stack<int, vector<int>>& a, stack<int, vector<int>>& b, stack<int, vector<int>>& c, int n)
////    {
////        if (n == 1)
////        {
////            c.push(a.top());
////            a.pop();
////            return;
////        }
////        dfs(a, c, b, n - 1);
////        c.push(a.top());
////        a.pop();
////        dfs(b, a, c, n - 1);
////    }
////
////    void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
////    {
////        /*
////        std::deque<int> mydeque (3,100);          // deque with 3 elements
////        std::vector<int> myvector (2,200);        // vector with 2 elements
////
////        std::stack<int> first;                    // empty stack
////        std::stack<int> second (mydeque);         // stack initialized to copy of deque
////
////        std::stack<int,std::vector<int> > third;  // empty stack using vector
////        std::stack<int,std::vector<int> > fourth (myvector);
////        */
////
////        // 已经排好序了
////        // 注意栈先进后出
////        // auto func = [](int f, int s)
////        // {
////        //     return f > s;// 注意栈先进后出
////        // }
////        // sort(A.begin(), A.end(), func);
////
////        stack<int, vector<int>>a(A), b, c;
////        int sz = A.size();
////        dfs(a, b, c, sz);
////
////        C.resize(sz);
////        for (int i = sz - 1; i >= 0; i--)
////        {
////            C[i] = c.top();
////            c.pop();
////        }
////    }
////};
////
////// 21. 合并两个有序链表
////// https://leetcode.cn/problems/merge-two-sorted-lists/submissions/584351340/
////
/////*
////子问题：将小的那一个连接到答案的后面，要l1, l2, l3
////解决子问题
////返回
////*/
////
////class Solution {
////public:
////    void dfs(ListNode* l1, ListNode* l2, ListNode* l3)
////    {
////        if (!l1)
////        {
////            l3->next = l2;
////            return;
////        }
////        else if (!l2)
////        {
////            l3->next = l1;
////            return;
////        }
////
////        if (l1->val < l2->val)
////        {
////            l3->next = l1;
////            l1 = l1->next;
////        }
////        else
////        {
////            l3->next = l2;
////            l2 = l2->next;
////        }
////
////        l3 = l3->next;
////        dfs(l1, l2, l3);
////    }
////
////    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
////    {
////        ListNode* p1 = list1, * p2 = list2, * p3;
////        p3 = new ListNode();
////        dfs(p1, p2, p3);
////        return p3->next;
////    }
////};
////
////// 206. 反转链表
////// https://leetcode.cn/problems/reverse-linked-list/
////
////class Solution {
////public:
////    void dfs(ListNode*& cur, ListNode*& next)
////    {
////        if (next == nullptr)
////            return;
////
////        ListNode* temp = next->next;
////        next->next = cur;
////        cur = next;
////        next = temp;
////        dfs(cur, temp);
////    }
////    ListNode* reverseList(ListNode* head)
////    {
////        ListNode* cur = nullptr, * next = head;
////        dfs(cur, next);
////        return cur;
////    }
////};
////
////// 24. 两两交换链表中的节点
////// https://leetcode.cn/problems/swap-nodes-in-pairs/
////
////// 交换最前面的两个节点，然后将后面的节点继续递归处理
////
////class Solution {
////public:
////    ListNode* swapPairs(ListNode* head)
////    {
////        if (!head)
////            return nullptr;
////        else if (!head->next)
////            return head;
////
////        ListNode* next = head->next, * nextt = head->next->next;
////        next->next = head;
////        head->next = swapPairs(nextt);
////
////        return next;
////    }
////};
////
////
////// 2331. 计算布尔二叉树的值
////// https://leetcode.cn/problems/evaluate-boolean-binary-tree/
////
////class Solution {
////public:
////    bool evaluateTree(TreeNode* root)
////    {
////        if (!root->left && !root->right)
////            return root->val;
////
////        if (root->val == 2)
////            return evaluateTree(root->left) | evaluateTree(root->right);
////        return evaluateTree(root->left) & evaluateTree(root->right);
////    }
////};
//
//
////// 129. 求根节点到叶节点数字之和
////// https://leetcode.cn/problems/sum-root-to-leaf-numbers/
////
////class Solution {
////public:
////    void dfs(TreeNode* root)
////    {
////        if (!root->left && !root->right)
////        {
////            v.push_back(s + to_string(root->val));
////            return;
////        }
////
////        s += to_string(root->val);
////        if (root->left)
////            dfs(root->left);
////        if (root->right)
////            dfs(root->right);
////        s.pop_back();
////    }
////
////    int sumNumbers(TreeNode* root)
////    {
////        if (!root->left && !root->right)
////            return root->val;
////
////        dfs(root);
////        int ret = 0;
////        for (auto& e : v)
////            ret += stoi(e);
////        return ret;
////    }
////private:
////    vector<string>v;
////    string s;
////};
//
////// 814. 二叉树剪枝
////// https://leetcode.cn/problems/binary-tree-pruning/
////
////class Solution {
////public:
////    void dfs(TreeNode* root, int& flag)
////    {
////        if (!root)
////            return;
////
////        // cout << "root->val = " << root->val << " flag = " << flag << endl;
////
////        int temp = 0;
////        flag = 0;
////        dfs(root->left, flag);
////        if (!flag)
////            root->left = nullptr;
////        temp |= flag;
////
////        flag = 0;
////        dfs(root->right, flag);
////        if (!flag)
////            root->right = nullptr;
////        temp |= flag;
////
////        flag = root->val | temp;
////    }
////
////    TreeNode* pruneTree(TreeNode* root)
////    {
////        if (!root)
////            return root;
////
////        int flag = root->val;
////        dfs(root, flag);
////        if (!(flag | root->val))
////            return nullptr;
////        return root;
////    }
////};
//
//#include <iostream>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <functional>
//#include <climits>
//#include <cstring>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//struct TreeNode {
//int val;
//struct TreeNode *left;
//struct TreeNode *right;
// 
//TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//};
// 
//// 98. 验证二叉搜索树
//// https://leetcode.cn/problems/validate-binary-search-tree/
//
//class Solution {
//public:
//    bool dfs(TreeNode* root, int flag)
//    {
//        if (!root)
//            return true;
//
//        if (!dfs(root->left, 1))// 左子树
//            return false;
//        if (root->val <= l)
//            return false;
//
//        if (!dfs(root->right, 2))// 右子树
//            return false;
//        if (root->val >= r)
//            return false;
//
//        if (flag == 1)
//        {
//            l = max(l, (ll)root->val);
//        }
//        else if (flag == 2)
//        {
//            r = min(r, (ll)root->val);
//        }
//        else
//
//        return true;
//    }
//
//    bool isValidBST(TreeNode* root)
//    {
//        if (!root)
//            return true;
//
//        if (!dfs(root, 0))
//            return false;
//        return true;
//    }
//private:
//    ll l = LLONG_MIN;// 要找最大值
//    ll r = LLONG_MAX;// 要找最小值
//    // unordered
//};
//
//// 函数声明
//TreeNode* buildTreeFromPreorderHelper(std::vector<int>& preorder, int& index);
//
//TreeNode * buildTreeFromPreorder(std::vector<int>&preorder) {
//    int index = 0; // 使用一个索引来追踪当前构造的节点
//    return buildTreeFromPreorderHelper(preorder, index);
//}
//
//TreeNode* buildTreeFromPreorderHelper(std::vector<int>& preorder, int& index) {
//    // 如果当前值为INT_MIN或者索引超出数组范围，返回空节点
//    if (index >= preorder.size() || preorder[index] == INT_MIN) {
//        return nullptr;
//    }
//
//    // 创建当前节点
//    TreeNode* node = new TreeNode(preorder[index]);
//    ++index; // 移动到下一个节点
//
//    // 递归构造左子树
//    node->left = buildTreeFromPreorderHelper(preorder, index);
//    ++index; // 移动到下一个节点
//    // 递归构造右子树
//    node->right = buildTreeFromPreorderHelper(preorder, index);
//
//    return node;
//}
//
//int main()
//{
//    TreeNode* root = nullptr;
//    vector<int>v = { 2,1,INT_MIN,INT_MIN,3,INT_MIN,INT_MIN, };
//    root = buildTreeFromPreorder(v);
//
//    cout << Solution().isValidBST(root);
//    return 0;
//}
//
//
//// 46. 全排列
//// https://leetcode.cn/problems/permutations/submissions/584578798/
//
//class Solution {
//public:
//    void dfs(vector<int>& nums)
//    {
//        if (v.size() == sz)
//        {
//            ans.push_back(v);
//            return;
//        }
//
//        for (int i = 0; i < sz; i++)
//        {
//            if (!book[i])
//            {
//                book[i] = 1;
//                v.push_back(nums[i]);
//                dfs(nums);
//                v.pop_back();
//                book[i] = 0;
//            }
//        }
//    }
//    vector<vector<int>> permute(vector<int>& nums)
//    {
//        sz = nums.size();
//        if (!sz)
//            return ans;
//        book.resize(sz);
//        dfs(nums);
//        return ans;
//    }
//private:
//    vector<int>v;
//    vector<vector<int>>ans;
//    vector<int>book;
//    int sz;
//};
//
//// 78. 子集
//// https://leetcode.cn/problems/subsets/
//
//// 两种解法：1、一个元素选还是不选      2、只选这个元素后面的元素（否则会重复）
//
//class Solution {
//public:
//    void dfs1(vector<int>& nums, int start)
//    {
//        if (start == nums.size())
//        {
//            ans.push_back(v);
//            return;
//        }
//
//        // 选该数
//        v.push_back(nums[start]);
//        dfs1(nums, start + 1);
//        v.pop_back();
//
//        // 不选该数
//        dfs1(nums, start + 1);
//    }
//
//    void dfs2(vector<int>& nums, int start)
//    {
//        ans.push_back(v);
//
//        for (int i = start; i < sz; i++)
//        {
//            v.push_back(nums[i]);
//            dfs2(nums, i + 1);
//            v.pop_back();
//        }
//    }
//
//    vector<vector<int>> subsets(vector<int>& nums)
//    {
//        sz = nums.size();
//        dfs1(nums, 0);
//        return ans;
//    }
//private:
//    vector<int>v;
//    vector<vector<int>>ans;
//    int sz;
//};

//
//// 50. Pow(x, n)
//// https://leetcode.cn/problems/powx-n/
//
//// 快速幂
//
///*
//1、快速幂不只是用于整数
//2、小数也能模
//3、推理：
//3 ^ 16 = (3 ^ 8) * (3 ^ 8)
//3 ^ 21 = (3 ^ 10) * (3 ^ 10) * 3
//*/
//
//class Solution {
//public:
//    double myPow(double x, long long n)
//    {
//        if (n == 1)
//            return x;
//        else if (n == 0)
//            return 1;
//
//        if (n > 0)
//        {
//            double temp = myPow(x, n / 2);
//            return n % 2 ? temp * temp * x : temp * temp;
//        }
//        else
//        {
//            return 1.0 / myPow(x, -n);// 注意n = INT_MAX时，-n超过int范围
//        }
//    }
//};
//
//// 超时
//// // int flag = 0;
//// // if (n < 0)
//// // {
//// //     flag = 1;
//// //     n = -n;
//// // }
//// // double ans = x;
//// // for (int i = 1; i <= n - 1; i++)
//// //     ans *= x;
//
//// // if (flag)
//// //     return 1.0 / ans;
//// // else
//// //     return ans;
//
//// 爆栈
//// if (n >= 0)
////     return x * myPow(x, n - 1);
//// else    
////     return 1.0 / myPow(x, -n/*注意是n次方*/);
//
//
////// 98. 验证二叉搜索树
////// https://leetcode.cn/problems/validate-binary-search-tree/
////
////// 用到二叉搜索树的性质：中序遍历是升序
////
////typedef long long ll;
////
////class Solution {
////public:
////    bool dfs(TreeNode* root)
////    {
////        if (!root)
////            return true;
////
////        if (!dfs(root->left))// 左子树
////            return false;
////
////        // cout << pre << " " << root->val << endl;
////
////        if (pre >= root->val)
////            return false;
////        pre = root->val;
////
////        if (!dfs(root->right))// 右子树
////            return false;
////
////        // 这里不需要验证，在中序遍历中，后续节点会帮忙验证的(๑•̀ㅂ•́)و✧
////        // 验证了会出错，如右子树为空时，这里一定会pre = root->val
////        // if (pre <= root->val)
////        //     return false;
////
////        return true;
////    }
////
////    // bool dfs(TreeNode* root)
////    // {
////    //     if (!root)
////    //         return true;
////
////    //     if (!dfs(root->left, 1))// 左子树
////    //         return false;
////    //     if (root->val <= l)
////    //         return false;
////
////    //     if (!dfs(root->right, 2))// 右子树
////    //         return false;
////    //     if (root->val >= r)
////    //         return false;
////
////    //     if (flag == 1)
////    //     {
////    //         l = max(l, (ll)root->val);
////    //         if (r != LLONG_MAX)
////    //             l = max(l, r);
////    //     }
////    //     else if (flag == 2)
////    //     {
////    //         r = min(r, (ll)root->val);
////    //         if (l != LLONG_MIN)
////    //             r = min(l, r);
////    //     }
////    //     return true;
////    // }
////
////    bool isValidBST(TreeNode* root)
////    {
////        if (!root)
////            return true;
////
////        if (!dfs(root))
////            return false;
////        return true;
////    }
////private:
////    // ll l = LLONG_MIN;// 要找最大值
////    // ll r = LLONG_MAX;// 要找最小值
////    // unordered
////    ll pre = LLONG_MIN;
////};
//
//
//// 230. 二叉搜索树中第 K 小的元素
//// https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
//
//// 法一：优先级队列
//class Solution1 {
//public:
//    void dfs(TreeNode* root)
//    {
//        if (!root)
//            return;
//        pq.push(root->val);
//        dfs(root->left);
//        dfs(root->right);
//    }
//
//    int kthSmallest(TreeNode* root, int k)
//    {
//        dfs(root);
//        k--;
//        while (k--)
//            pq.pop();
//        return pq.top();
//    }
//private:
//    priority_queue<int, vector<int>, greater<int>>pq;
//};
//
//// 法二：利用二叉搜索树中序是升序的特性
//class Solution {
//public:
//    void dfs(TreeNode* root)
//    {
//        if (!num || !root)
//            return;
//
//        dfs(root->left);
//        if (!num)
//            return;
//
//        num--;
//        ans = root->val;
//
//        dfs(root->right);
//        if (!num)
//            return;
//    }
//
//    int kthSmallest(TreeNode* root, int k)
//    {
//        num = k;
//        dfs(root);
//        return ans;
//    }
//private:
//    int num;
//    int ans;
//};
//
//
//// 257. 二叉树的所有路径
//// https://leetcode.cn/problems/binary-tree-paths/
//
//class Solution {
//public:
//    void dfs(TreeNode* root)
//    {
//        if (!root)
//            return;
//
//        string temp = to_string(root->val);
//        if (path.size())
//            path += "->";
//
//        path += temp;
//        if (!root->left && !root->right)// 叶子节点才处理结果
//            v.push_back(path);
//        else
//        {
//            dfs(root->left);
//            dfs(root->right);
//        }
//
//        int len = temp.size();
//        path.resize(path.size() - len);
//        if (path.size())
//            path.resize(path.size() - 2);
//    }
//
//    vector<string> binaryTreePaths(TreeNode* root)
//    {
//        dfs(root);
//        return v;
//    }
//private:
//    vector<string>v;
//    string path;
//};
//
//
//// 1863. 找出所有子集的异或总和再求和
//// https://leetcode.cn/problems/sum-of-all-subset-xor-totals/
//
//// 子集就是组合
//
//class Solution {
//public:
//    void dfs(vector<int>& nums, int start)
//    {
//        ans.push_back(sum);
//
//        for (int i = start; i < sz; i++)
//        {
//            sum ^= nums[i];
//            dfs(nums, i + 1);
//            sum ^= nums[i];
//        }
//    }
//
//    int subsetXORSum(vector<int>& nums)
//    {
//        sz = nums.size();
//        dfs(nums, 0);
//        int ret = 0;
//        for (auto& e : ans)
//            ret += e;
//        return ret;
//    }
//private:
//    vector<int>ans;
//    int sz;
//    int sum = 0;
//};
//
////47. 全排列 II
////https://leetcode.cn/problems/permutations-ii/
//
//// 注意有重复元素
//
//// 1、同一个节点的分支中，一个数值的数字只能选一个  2、选过的数不要选
//
//class Solution {
//public:
//    void dfs(vector<int>& nums)
//    {
//        if (v.size() == sz)
//        {
//            ans.push_back(v);
//            return;
//        }
//
//        unordered_map<int, int>mp;
//        for (int i = 0; i < sz; i++)
//        {
//            if (!book[i] && !mp[nums[i]])
//            {
//                mp[nums[i]] = 1;// 1、同一个节点的分支中，一个数值的数字只能选一个
//                book[i] = 1;//  2、选过的数不要选
//                v.push_back(nums[i]);
//                dfs(nums);
//                v.pop_back();
//                book[i] = 0;
//            }
//        }
//    }
//
//    vector<vector<int>> permuteUnique(vector<int>& nums)
//    {
//        sz = nums.size();
//        if (!sz)
//            return ans;
//        book.resize(sz);
//        dfs(nums);
//        return ans;
//    }
//private:
//    vector<int>v;
//    vector<vector<int>>ans;
//    vector<int>book;
//    int sz;
//};
//
//
//// 77. 组合
//// https://leetcode.cn/problems/combinations/
//
//class Solution {
//public:
//    void dfs(int n, int k, int start)
//    {
//        if (v.size() == k)
//        {
//            ans.push_back(v);
//            return;
//        }
//
//        for (int i = start; i <= n; i++)
//        {
//            if (!book[i])
//            {
//                book[i] = 1;
//                v.push_back(i);
//                dfs(n, k, i + 1);
//                v.pop_back();
//                book[i] = 0;
//            }
//        }
//    }
//    vector<vector<int>> combine(int n, int k)
//    {
//        book.resize(n + 1);
//        dfs(n, k, 1);
//        return ans;
//    }
//private:
//    vector<int>v;
//    vector<int>book;
//    vector<vector<int>>ans;
//};


#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#include <climits>
#include <cstring>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

//// 494. 目标和
//// https://leetcode.cn/problems/target-sum/
//
//// 和《子集》那一题差不多，那一题是选和不选，这一题是加和减
//
//class Solution {
//public:
//    void dfs(vector<int>& nums, int target, int start)
//    {
//        if (start == nums.size())
//        {
//            if (sum == target)
//                ans++;
//            return;
//        }
//
//        sum += nums[start];
//        dfs(nums, target, start + 1);
//        sum -= nums[start];
//
//        sum -= nums[start];
//        dfs(nums, target, start + 1);
//        sum += nums[start];
//    }
//
//    int findTargetSumWays(vector<int>& nums, int target)
//    {
//        dfs(nums, target, 0);
//        return ans;
//    }
//private:
//    int sum = 0;
//    int ans = 0;
//};

//// 22. 括号生成
//// https://leetcode.cn/problems/generate-parentheses/
//
//
//// 法一：我的写法，用栈检查有没有出现非法组合
//class Solution1 {
//public:
//    bool check()
//    {
//        stack<char>temp;
//        if (!num1 && !num2)
//        {
//            for (auto& e : s)
//            {
//                if (e == '(')
//                    temp.push('(');
//                else
//                {
//                    if (!temp.size())
//                        return false;
//                    else
//                        temp.pop();
//                }
//            }
//            return !temp.size();
//        }
//        else
//        {
//            temp = st;
//            if (temp.top() == ')')
//            {
//                temp.pop();
//                if (!temp.size())// 第一个是')'
//                    return false;
//            }
//            else
//            {
//                if (!num2)// 最后一个是'('
//                    return false;
//            }
//        }
//
//        return true;
//    }
//
//    void dfs(int n)
//    {
//        if (st.size() && !check())
//            return;
//
//        if (s.size() == 2 * n)
//        {
//            v.push_back(s);
//            return;
//        }
//
//        if (num1)
//        {
//            num1--;
//            s += '(';
//            st.push('(');
//            dfs(n);
//            st.pop();
//            s.pop_back();
//            num1++;
//        }
//
//        if (num2)
//        {
//            num2--;
//            s += ')';
//            st.push(')');
//            dfs(n);
//            s.pop_back();
//            num2++;
//        }
//    }
//
//    vector<string> generateParenthesis(int n)
//    {
//        num1 = num2 = n;
//        dfs(n);
//        return v;
//    }
//private:
//    vector<string>v;
//    string s;
//    int num1;
//    int num2;
//    stack<char>st;
//};
//
//// 法二：老师写法，1、左括号数 = 右括号数       2、任何一个字串，左括号数 >= 右括号数
//class Solution {
//public:
//    void dfs(int n)
//    {
//        if (right == n)
//        {
//            v.push_back(s);
//            return;
//        }
//
//        if (left < n)
//        {
//            left++;
//            s += '(';
//            dfs(n);
//            s.pop_back();
//            left--;
//        }
//
//        if (right < left)
//        {
//            right++;
//            s += ')';
//            dfs(n);
//            s.pop_back();
//            right--;
//        }
//    }
//
//    vector<string> generateParenthesis(int n)
//    {
//        dfs(n);
//        return v;
//    }
//private:
//    vector<string>v;
//    string s;
//    int left = 0;
//    int right = 0;
//};
//
//// 784. 字母大小写全排列
//// https://leetcode.cn/problems/letter-case-permutation/
//
//class Solution {
//public:
//    void dfs(string s, int start)
//    {
//        if (start == s.size())
//        {
//            ans.push_back(path);
//            return;
//        }
//
//        if (s[start] >= 'a' && s[start] <= 'z')
//        {
//            path += s[start];
//            dfs(s, start + 1);
//            path[start] = s[start] - ('a' - 'A');
//            dfs(s, start + 1);
//            path.pop_back();
//        }
//        else if (s[start] >= 'A' && s[start] <= 'Z')
//        {
//            path += s[start];
//            dfs(s, start + 1);
//            path[start] = s[start] + ('a' - 'A');
//            dfs(s, start + 1);
//            path.pop_back();
//        }
//        else
//        {
//            path += s[start];
//            dfs(s, start + 1);
//            path.pop_back();
//        }
//    }
//
//    vector<string> letterCasePermutation(string s)
//    {
//        dfs(s, 0);
//        return ans;
//    }
//private:
//    vector<string>ans;
//    string path;
//};
//
//// 526. 优美的排列
//// https://leetcode.cn/problems/beautiful-arrangement/
//
//// 注意只用满足两个条件之一
//
//class Solution {
//public:
//    void dfs(int n, int start)
//    {
//        if (start == n + 1)
//        {
//            ans++;
//            return;
//        }
//
//        // perm[start] = i
//        for (int i = 1; i <= n; i++)
//        {
//            if (!book[i] && (start % i == 0 || i % start == 0))
//            {
//                book[i] = 1;
//                perm[start] = i;
//                dfs(n, start + 1);
//                book[i] = 0;
//            }
//        }
//    }
//
//    int countArrangement(int n)
//    {
//        perm.resize(n + 1);
//        book.resize(n + 1);
//        dfs(n, 1);
//        return ans;
//    }
//private:
//    int ans = 0;
//    vector<int>perm;
//    vector<int>book;
//};

// 36. 有效的数独
// https://leetcode.cn/problems/valid-sudoku/

class Solution {
public:
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        if (i == 9 || j == 9 || board[i][j] != '.')
            return;
        if (h[i].size() == 9 || l[j].size() == 9)
            return;

        int x = i / 3 * 3, y = j / 3 * 3;
        if (s[{x, y}].size() == 9)
            return;

        for (int k = 1; k <= 9; k++)
        {
            if (h[i][k] == 0 && l[j][k] == 0 && s[{x, y}][k] == 0)
            {
                board[i][j] = k + '0';

                for (int a = i; a < 9; a++)
                    for (int b = j; b < 9; b++)
                        if (board[i][j] == '.')
                            dfs(board, a, b);
            }
        }
    }

    bool isValidSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    h[i][board[i][j] - '0'] = 1;
                    l[j][board[i][j] - '0'] = 1;
                    int t = board[i][j] - '0';
                    s[{i / 3 * 3, j / 3 * 3}][t] = 1;
                }
            }
        dfs(board, 0, 0);
        for (int i = 0; i < 9; i++)
        {
            if (h[i].size() < 9)
                return false;
            for (int j = 0; j < 9; j++)
                if (l[j].size() < 9)
                    return false;
        }

        return true;
    }
private:
    vector<unordered_map<int, int>>h;
    vector<unordered_map<int, int>>l;
    unordered_map<pair<int, int>, int>s;
};

int main()
{
    vector<int>v = { 1, 1, 1, 1, 1 };
    Solution().isValidSudoku(3);
    //Solution().findTargetSumWays(vector<int>({ 1, 1, 1, 1, 1 }), 3);
    return 0;
}